#ifndef _MYSTACK_H
#define _MYSTACK_H

#include <stddef.h>
#include <algorithm>

template <typename T>
class mystackimpl
{
public:
    mystackimpl(size_t size=0)
        : m_data(NULL), m_size(size), m_used(0) {
        /*
         * Allocate raw memory to avoid initialization of objects.
         * This removes requirement on the default constructor of T.
         */
        m_data = (size==0) ? NULL : (T *)operator new(sizeof(T)*m_size);
    }
    ~mystackimpl() {
        while (m_used != 0) {
            destroy(m_data+m_used-1);
            --m_used;
        }
        operator delete(m_data);
    }
    void swap(mystackimpl &other) {
        std::swap(m_data, other.m_data);
        std::swap(m_size, other.m_size);
        std::swap(m_used, other.m_used);
    }
    void construct(T *p, const T &v) {
        new (p) T(v);
    }
    void destroy(T *p) {
        p->~T();
    }
protected:
    T *m_data;
    size_t m_size;
    size_t m_used;
private:
    mystackimpl(const mystackimpl &other);
    mystackimpl &operator=(const mystackimpl &other);
};

/*
 * Using mystackimpl as a member object should be better.
 * Inheritance is nearly the strongest relationship in C++(second only to friendship).
 */
template <typename T>
class mystack : private mystackimpl<T>
{
public:
    /*
     * This is necessary when a template-derived-class uses a member it inherits from its template-base-class.
     * http://www.parashift.com/c++-faq-lite/nondependent-name-lookup-members.html
     */
    using mystackimpl<T>::m_data;
    using mystackimpl<T>::m_size;
    using mystackimpl<T>::m_used;
    explicit mystack(size_t size=0)
        : mystackimpl<T>(size) {
    }
    /* default destructor is fine */
    /* ~mystack(); */
    mystack(const mystack &other)
        : mystackimpl<T>(other.m_used) {
        while (m_used < other.m_used) {
            /*
             * Use copy constructor to remove requirement on copy assignment.
             */
            construct(m_data+m_used, other.m_data[m_used]);
            ++m_used;
        }
    }
    mystack &operator=(const mystack &other) {
        mystack(other).swap(*this);
        return *this;
    }
    size_t size() const {
        return m_used;
    }
    bool empty() const {
        return m_used == 0;
    }
    void push(const T &t) {
        if(m_used < m_size) {
            construct(m_data+m_used, t);
            ++m_used;
        } else {
            mystack temp(m_size*2+1);
            while (temp.m_used < m_used) {
                temp.push(m_data[temp.m_used]);
            }
            temp.push(t);
            swap(temp);
        }
    }
    void pop() {
        /*
         * Separate pop() and top() here.
         * If the the top element is returned in pop(), the copy constructor of T requires nothrow.
         * Otherwise, the popped value is lost forever.
         */
        if (m_used == 0) {
            throw "pop from empty stack";
        }
        --m_used;
        destroy(m_data+m_used);
    }
    T &top() {
        if (m_used == 0) {
            throw "empty stack";
        }
        return m_data[m_used-1];
    }
};

#endif
